package my.heap;

import java.util.Comparator;

/**
 * <p>
 * 二叉堆
 * </p>
 *
 * @author AJun
 * @since 2020/9/11
 */
@SuppressWarnings("ALL")
public class BinaryHeap<E> extends AbstractHeap<E> {

    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Heapify 批量建堆
     */
    public BinaryHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);

        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            this.size = elements.length; // 元素数量是批量建堆给的数据的大小
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            // 批量建堆
            heapify();
        }
    }

    public BinaryHeap() {
        this(null, null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    public BinaryHeap(E[] elements) {
        this(elements, null);
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        // 上滤
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyCheck();
        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        // 下滤
        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);

        E root = null;
        if (size == 0) {
            // 如果本来就没有元素，就直接添加
            elements[size++] = element;
        } else {
            // 如果有元素，则删除堆顶元素后再添加
            root = elements[0]; // 要被删除的堆顶元素
            elements[0] = element; // 使用新添加的元素替换掉堆顶元素
            siftDown(0); // 让新添加的元素下滤
        }
        return root;
    }

    /**
     * 批量建堆
     */
    private void heapify() {
        // 自上而下的上滤，效率较低 O(nlogn)
        /*for (int i = 1; i < size; i++) {
            siftUp(i);
        }*/

        // 自下而上的下滤，推荐这种，效率较高 O(n)
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 让 index 位置的元素上滤
     *
     * @param index 元素索引
     */
    private void siftUp(int index) {
        E element = elements[index];
        // index > 0 表示该节点有父节点
        while (index > 0) {
            // 获取该节点的父节点索引(公式)
            int parentIndex = (index - 1) >> 1;
            E parent = elements[parentIndex];
            // 小于等于父元素，退出循环
            if (compare(element, parent) <= 0)
                break;
            // 大于父元素，将父元素存储在 index 位置
            elements[index] = parent;
            // 重新对 index 赋值
            index = parentIndex;
        }
        elements[index] = element;
    }

    /**
     * 让 index 位置的元素下滤
     *
     * @param index 元素索引
     */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1; // 公式
        // 必须保证 index 位置是非叶子节点，第一个叶子节点的索引就是非叶子节点的数量
        while (index < half) {
            // index 位置的节点有俩种情况
            // 1.只有左子节点
            // 2.同时有左右子节点

            // 默认使用左子节点和要删除的元素进行比较
            int childIndex = (index << 1) + 1; // 公式
            E child = elements[childIndex];
            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的
            if (rightIndex < size && compare(elements[rightIndex], child) > 0)
                child = elements[childIndex = rightIndex];
            // 要删除元素大于子节点元素
            if (compare(element, child) >= 0)
                break;
            // 要删除元素小于子节点元素，将子节点存放到 index 位置
            elements[index] = child;
            // 重新对 index 赋值
            index = childIndex;
        }
        elements[index] = element;
    }

    /**
     * 扩容，保证要具备 capacity 的容量大小
     *
     * @param capacity 容量大小
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;

        // 扩容，每次扩容旧容量的 1.5 倍, 位运算效率高, oldCapacity >> 1(右移一位) = oldCapacity/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++)
            newElements[i] = elements[i];
        elements = newElements;
    }

    private void emptyCheck() {
        if (size == 0)
            throw new IndexOutOfBoundsException("Heap is empty");
    }

    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("Element must not be null");
    }

}
